package hot_100;

import java.util.*;

public class 三数之和 {
    public static void main(String[] args) {

    }

    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int k = n - 1;
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                while (k > j && nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                }
                if (j == k)
                    break;
                if (nums[i] + nums[j] + nums[k] == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    Collections.addAll(list, nums[i], nums[j], nums[k]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    //低效解法
/*    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        HashMap<ArrayList<Integer>, Integer> map = new HashMap<>();
        for (int i = 0; i < n && nums[i] <= 0; i++) {
            int st = i + 1, ed = n - 1;
            while (ed > st) {
                int temp = nums[i] + nums[st] + nums[ed];
                if (temp > 0) {
                    ed--;
                } else if (temp < 0) {
                    st++;
                } else {
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    Collections.addAll(arrayList, nums[i], nums[st], nums[ed]);
                    map.putIfAbsent(arrayList, 1);
                    st++;
                }
            }
        }
        return new ArrayList<>(map.keySet());
    }*/
}
